#include <bits/stdc++.h>
#define int long long
#define ls tree[x].lson
#define rs tree[x].rson
using namespace std;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int t,n,a[2001],vis[1000001],maxn,near[2001],sum[2001][2001],dp[2001][2001];//now:i pre same coloer:j mycolor:k
bool color[21];
void dfs(int x)
{
    if(x==n+1)
    {
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=i-1;j>=1;j--)
            {
                if(color[i]==color[j])
                {
					if(a[i]==a[j])
						ans+=a[i];
                    break;
                }
            }
        }
        maxn=max(maxn,ans);
        return;
    }
    color[x]=true;
    dfs(x+1);
    color[x]=false;
    dfs(x+1);
}
signed main()
{
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    t=read();
    while(t--)
    {
        n=read();
        for(int i=1;i<=n;i++)
        {
            a[i]=read();
        }
        if(n<=15)
        {
            maxn=0;
            dfs(1);
            printf("%lld\n",maxn);
        }
        else
        {
            memset(vis,0,sizeof(vis));
            for(int i=1;i<=n;i++)
            {
                near[vis[a[i]]]=i;
                vis[a[i]]=i;
            }
            for(int i=1;i<=n;i++)
            {
				for(int j=i+1;j<=n;j++)
				{
					sum[i][j]=sum[i][j-1];
					if(a[j]==a[j-1])
					{
						sum[i][j]+=a[j];
					}
				}
            }
            //cout<<"6"<<endl;
            for(int l=1;l<=n;l++)
            {
				for(int r=l+1;r<=n;r++)
				{
					for(int k=l-1;k<=r-1;k++)
					{
						dp[l][r]=max(dp[l-1][k]+dp[k][r-1],sum[k-1][r-1]+sum[l-1][k-1])+a[l]*(a[l]==a[r]);
					}
				}
			}
			printf("%lld\n",dp[1][n]);
        }
    }
    return 0;
}
